package leetcode;

import java.util.*;

public class LeetCode47 {

    public static void main(String[] args) {
        LeetCode47 leetCode47 = new LeetCode47();
        System.out.println(leetCode47.permuteUnique(new int[]{1, 1, 2}));
    }

    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        int[] used = new int[nums.length];
        Set<String> set = new HashSet<>();
        helper(nums, used, new ArrayList<>(), 0, "", set);
        return result;
    }

    private void helper(int[] nums, int[] used, List<Integer> list, int step, String s, Set<String> set) {
        int n = nums.length;
        if (n == step && !set.contains(s)) {
            result.add(list);
            set.add(s);
        } else {
            for (int i = 0; i < n; i++) {
                if (used[i] == 0) {
                    used[i] = 1;
                    List<Integer> tmp = new ArrayList<>(list);
                    tmp.add(nums[i]);
                    helper(nums, used, tmp, step + 1, s + nums[i], set);
                    used[i] = 0;
                }
            }
        }
    }
//------------------------------------------------------------------
}
